package company.bytedance

import kotlinetc.createNodeList
import kotlinetc.println
import kotlinetc.toList
import leetcode.ListNode


fun main(args: Array<String>) {


    // O(N) 时间复杂度，O(1)复杂度
    val nums = arrayOf(-1, 2, 4, -9, 7, 8, -12, 10, 0)
    setParted(nums)

    nums.toList().println()


    val nodeList = createNodeList("1->2->3->4->5->6")

    nodeList.toList().println()

    reverNodeList(nodeList)?.toList()?.println()


    val nodeList1 = createNodeList("7->8->9->10->11->12")

    nodeList1.toList().println()

    reverseNodeList1(nodeList1).toList().println()

}


fun setParted(nums: Array<Int>) {

    if (nums.isEmpty())
        return

    var s = 0

    var p = nums.lastIndex

    while (s <= p) {

        //move until meet positive number
        while (nums[s] < 0 && s < p) s++


        //move until  meet negative number
        while (nums[p] > 0 && s < p) p--

        if (nums[s] > 0 && nums[p] < 0) {
            val t = nums[s]
            nums[s] = nums[p]
            nums[p] = t
        } else {
            // nums now  is already sorted
            break
        }

    }
}

// node1 ---->node2 ----> node3------->node4
fun reverNodeList(head: ListNode?): ListNode? {

    if (head?.next == null)
        return head

    var curr: ListNode? = head
    var prev: ListNode? = null
    var next: ListNode? = head?.next

    //当前节点的下一个节点
    // 前一个节点更新为当前节点
    //当前节点 更新为下一个节点

    while (curr?.next != null) {

        curr.next = prev

        prev = curr

        curr = next

        next = curr?.next
    }

    curr?.next = prev

    return curr

}

fun reverseNodeList1(head: ListNode?): ListNode? {

    if (head?.next == null)
        return head

    val nestedHeader = reverseNodeList1(head.next)

    head.next?.next = head

    head.next = null

    return nestedHeader

}